In a computer network or internetwork, there is a problem of physically routing message traffic (data packets) between nodes and providing the shortest path between any two nodes. A computer network is formed of three or more nodes connected by links. Each node may be a general-purpose computer or a specialized device, such as a router or switch. A link is a communication path that connects two or more nodes with one another. An internetwork is formed of multiple computer networks interconnected by nodes, each node may be a general-purpose computer or a specialized device, such as a router. Each link has a length (or cost) associated with it. A bidirectional link has a length in each of its two directions. A broadcast link has a single cost. A network path also has a single length or cost associated with it. Once a shortest path is provided, the number of nodes or the length of a link in the network may change so that a new shortest path must be found. Because providing a shortest path uses computer resources, and because routing traffic inefficiently wastes network resources, it is important to quickly and accurately find each shortest path.
Data packets may, for example, be routed from an end station in one network to an end station in another network. The devices that route the data packets (routers) map the address of a destination network or end station into either a path or the next router (or successor) along the path to the destination. To accomplish their function, routers need to implement a routing protocol, which supports two main functions: route computation and data packet forwarding.
Three types of approaches exist in the prior art for providing a shortest path. The first type is the link-state approach (also called a topology-broadcast approach), wherein a node must know the entire network topology. Each router uses this information to compute the shortest path and successor router (or next hop) in the path to each destination. The node broadcasts update messages to every node in the network or internetwork. Each node originates update messages containing the cost of the links adjacent to that node and forwards updates received from other nodes, taking care to ensure that the same update is not forwarded more than once. Well known examples of the link-state approach are the new ARPANET routing protocol and the OSPF (Open Shortest Path First) protocol. A primary disadvantage of the link-state approach is that the maintenance of an up-to-date version of the entire network topology at every node may constitute excessive storage and communication overhead in a large network. Another disadvantage is that the path computations required by the link-state approach are computationally expensive. A third disadvantage is that the shortest perceived path may contain loops, which lengthen a path and cause data packers to visit the same node multiple times. The existence of loops, even temporarily, is a detriment to overall performance of a computer network.
The distance-vector approach requires that a router knows only the distances to its own destinations and to those destinations reported by other nodes, together with some additional information that varies depending on the particular protocol. The router maintains the length of the shortest path from each of its adjacent nodes to every destination node and the next node in that shortest path. The node sends update message, containing (as a minimum) distance to other nodes, to only its adjacent nodes. Well known examples of the distance vector approaches are RIP (Routing Information Protocol), RIPv2 (RIP version 2), BGP (Border Gateway Routing Protocol), and Cisco's proprietary EIGRP (Enhanced Interior Gateway Routing Protocol).
RIP and RIPv2 use variants of the distributed Bellman-Ford (DBF) algorithm for shortest-path computation. The main disadvantages of protocols based on DBF are the creation of routing loops and the possibility of counting to infinity. A node counts to infinity when it increments its distance to a destination node, until a predefined maximum value is reached. A number of attempts have been made to solve the counting to infinity and looping problems by increasing the amount of information exchanged among nodes or by making nodes disregard link changes for a predefined period of time before updating their routing tables. None of these approaches, however, has been successful.
BGP includes the complete path to a destination in a routing-table update. Because nodes can determine if they are part of a path reported by a neighbor node to a destination, they avoid long-term loops and counting to infinity.
A patent illustrative of the distance vector approach is U.S. Pat. No. 4,466,060 to Riddle. The Riddle patent disclosed an adaptive distributed message routing algorithm where each node transmits different information to its adjacent nodes. The transmitted routing information arranges the nodes of the network in a hierarchical fashion that takes on the graphical form of a tree structure with the transmitting node at the root of the tree and the remaining nodes stemming from the root. A similar approach to the Riddle patent is used by Garcia-Luna-Aceves and Murthy in "path finding algorithms" (J. J. Garcia-Luna-Aceves and S. Murthy, "A Path-Finding Algorithm for Loop-Free Routing," IEEE/ACM Transactions on Networking, February 1997) as well as others (e.g., P. Humblet, "Another Adaptive Shortest-Path Algorithm", IEEE Transactions on Communications, Vol.39, No.6, June 1991, pp. 995-1003; B. Rajagopalan and M. Faiman, "A Responsive Distributed Shortest-Path Routing Algorithm within Autonomous Systems," Internetworking: Research and Experience, Vol.2, No.1, March 1991, pp. 51-69). In this type of distance-vector algorithms, a node communicates to its neighbors its shortest path routing tree by incrementally sending the distance and second-to-last hop node identifier to each destination. These algorithms eliminate counting to infinity, and the loop-free path finding algorithm by Garcia-Luna-Aceves and Murthy eliminates routing loops as well.
EIGRP eliminates counting to infinity and looping using the Diffusing Update Algorithm (DUAL) (J. J. Garcia-Luna-Aceves, "Loop-Free Routing Using Diffusing Computations," IEEE/ACM Transactions on Networking, Vol. 1, No. 1, February 1993). DUAL selects routes to be inserted into a routing table based on feasible successors. A successor is a neighboring router used for packet forwarding that has a least-cost path to a destination that is guaranteed not to be part of a routing loop. From router i's standpoint, a feasible successor toward destination j is a neighbor router k that satisfies a feasibility condition that is based on values such as the router's own distance and its neighbor's distance to the destination.
The three feasibility conditions in the prior art are the DIC (Distance Increase Condition) and the CSC (Current Successor Condition) and the SNC (Source Node Condition). The DIC can be summarized as follows: If a node i detects a decrease in either
1. the length of a link to one of its adjacent neighbors or PA1 2. the distance from an adjacent node to a destination node PA1 1. the length of a link to one of its adjacent neighbors or PA1 2. the distance from an adjacent node to a destination node PA1 1. the length of a link to one of its adjacent neighbors or PA1 2. the distance from an adjacent node to a destination node
then node i can choose any adjacent neighbor as the new successor node en route to the destination node, provided that the sum of the length from node i to the adjacent neighbor and the length from the adjacent neighbor to the destination node is less than or equal to the smallest assigned length from node i to the destination node.
The CSC can be summarized as: If a node i detects a change in either
then node i can choose any adjacent neighbor as the new successor node en route to the destination node, provided that the length from the new adjacent neighbor to the destination node is less than or equal to the smallest assigned length from the original adjacent neighbor to the destination node.
The SNC can be summarized as: If a node i detects a change in either
then node i can chose any new adjacent neighbor as long as the length from the adjacent neighbor to the destination node is less than the feasible distance from node i to the destination. The feasible distance is the minimum of all of the distances to the destination that node i has reported since the last time node i either initialized itself or began its participation in a diffusing computation.
When the feasibility condition is met, node i can carry out a local computation to determine a new path independently of other nodes, thus saving computational resources. It is important to realize, however, that the feasibility conditions DIC, CSC, and SNC are not always met. When a feasibility condition is not met at a node i, node i must perform a diffusing computation, wherein node i must coordinate with other nodes to find a new shortest path. The SNC can be met easier than the DIC or CSC, for example, and thus the SNC allows for fewer diffusing computations than these other feasibility conditions. Therefore, because it is important to meet a feasibility condition as often as possible to save computational resources, there has been a need to develop feasibility conditions that can be more easily satisfied in order to avoid diffusing computations as much as possible.
As mentioned above, diffusing computations require larger amounts of computer resources than local computations. One prior art system supports multiple diffusing computations concurrently by maintaining bit vectors at each node. The bit vectors specify, for each adjacent node and for each destination node, the number of correspondences which were originated by and the number of correspondences which must be answered by the node maintaining the bit vector. The problem with this system is that the bit vectors can become exceedingly large in a large network, thus consuming large amounts of computational resources. Another prior art system eliminates these bit vectors by requiring a node to `freeze` a designated successor as long as the node is part of the diffusing computation (i.e., while a diffusing computation proceeds for a particular destination, each node participating in the diffusing computation for that destination must keep the same next hop for that destination). In addition, a node is only allowed to participate in one diffusing computation at a time for each destination. A state machine is used to process messages that arrive at a node while the node participates in a diffusing computation, and determines if a new diffusing computation is necessary after the previous one terminates. This prior art system classifies routing messages as updates, queries, and replies. Queries and replies are used for coordinating diffusing computations. In all of the prior art systems based on diffusing computations and feasibility conditions, the feasibility conditions are based on the current value of link costs and of distances reported by neighbors, and a node raises its feasible distance only when it starts or joins a diffusing computation.
Thus, even though diffusing computations of the prior art may provide correct results, they are inefficient. Because of this inefficiency, there has been a need in the prior art to develop new approaches to diffusing computations which are able to conserve computational and communication resources. In addition, while prior art systems based on feasibility conditions can provide multipath routing in the absence of diffusing computations, these systems can provide only a single successor during the course of a diffusing computation, and must wait until the diffusing computation terminates before providing a better path. The result of this constraint is that even if a better path to the destination is becomes available, that path cannot be used until the diffusing computation terminates.
The third approach to routing in computer networks and internetworks is the approach based on link vector algorithms (J. J. Garcia-Luna-Aceves and J. Behrens, "Distributed, Scalable Routing based on Vectors of Link States," IEEE Journal on Selected Areas in Communications, Vol 13, No. 8, October 1995). The basic idea of LVA consists of asking each node to report to its neighbors the characteristics of each of the links it uses to reach a destination through one or more preferred paths, and to report to its neighbors which links it has erased from its preferred paths. Using this information, each router constructs a source graph consisting of all the links it uses in the preferred paths to each destination. LVA ensures that the link-state information maintained at each router corresponds to the link constituency of the preferred paths used by routers in the network or internet. Each router runs a local algorithm or multiple algorithms on its topology table to compute its source graph with the preferred paths to each destination. Such algorithms can be any type of algorithm (e.g., shortest path, maximum-capacity path, policy path) and the only requirements for correct operation are for all routers to use the same algorithm to compute the same type of preferred paths, and that routers report all the links used in all preferred paths obtained. The disadvantage of LVA is that it may allow temporary routing loops to occur in the network or internetwork.